¿Por qué procesar una matriz ordenada es más rápido que procesar una matriz no ordenada?

Eres víctima de un error de predicción de rama.
¿Qué es la predicción de ramas?
Considere un cruce de ferrocarril:
Imagen de Mecanismo, vía Wikimedia Commons. Usado bajo la licencia CC-By-SA 3.0.
Ahora, por el bien de la discusión, supongamos que esto se remonta al siglo XIX, antes de las comunicaciones de larga distancia o por radio.
Usted es el operador de un cruce y escucha que se acerca un tren. No tienes idea de qué camino se supone que debe tomar. Detienes el tren para preguntarle al conductor en qué dirección quieren. Y luego configura el interruptor apropiadamente.
Los trenes son pesados ​​y tienen mucha inercia. Por tanto, tardan una eternidad en empezar y reducir la velocidad.
¿Existe una forma mejor? ¡Adivina en qué dirección irá el tren!
Si acertó, continúa.
Si adivinó mal, el capitán se detendrá, retrocederá y le gritará que active el interruptor. Entonces puede reiniciar por el otro camino.
Si aciertas siempre, el tren nunca tendrá que detenerse. Si adivina mal con demasiada frecuencia, el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciando.
Considere una instrucción if: a nivel de procesador, es una instrucción de bifurcación:
Eres un procesador y ves una rama. No tienes idea de qué camino tomará. ¿Qué haces? Detiene la ejecución y espera hasta que se completen las instrucciones anteriores. Luego continúas por el camino correcto.
Los procesadores modernos son complicados y tienen procesos largos. Así que tardan una eternidad en "calentarse" y "reducir la velocidad".
¿Existe una forma mejor? ¡Adivinas en qué dirección irá la rama!
Si acertó, continúa ejecutando.
Si adivinó mal, debe limpiar la tubería y regresar a la rama. Entonces puedes reiniciar por el otro camino.
Si aciertas siempre, la ejecución nunca tendrá que detenerse. Si adivina mal con demasiada frecuencia, pasa mucho tiempo estancando, retrocediendo y reiniciando.
Esta es la predicción de rama. Admito que no es la mejor analogía, ya que el tren podría señalar la dirección con una bandera. Pero en las computadoras, el procesador no sabe en qué dirección irá una rama hasta el último momento.
Entonces, ¿cómo adivinaría estratégicamente para minimizar la cantidad de veces que el tren debe retroceder y tomar el otro camino? ¡Miras la historia pasada! Si el tren sale a la izquierda el 99% del tiempo, entonces supongo que se fue. Si se alterna, alterna tus conjeturas. Si sale en una dirección cada tres veces, adivinas lo mismo ...
En otras palabras, intentas identificar un patrón y seguirlo. Así es más o menos cómo funcionan los predictores de rama.
La mayoría de las aplicaciones tienen ramas que se comportan bien. Por lo tanto, los predictores de rama modernos generalmente alcanzarán tasas de acierto> 90%. Pero cuando se enfrentan a ramas impredecibles sin patrones reconocibles, los predictores de ramas son prácticamente inútiles.
Más información: artículo sobre "Predictor de ramas" en Wikipedia.
Como se insinuó desde arriba, el culpable es esta declaración if:
si (dato [c]> = 128)
suma + = datos [c];
Observe que los datos se distribuyen uniformemente entre 0 y 255. Cuando se ordenan los datos, aproximadamente la primera mitad de las iteraciones no entrará en la instrucción if. Después de eso, todos ingresarán la declaración if.
Esto es muy amigable para el predictor de rama ya que la rama va consecutivamente en la misma dirección muchas veces. Incluso un simple contador de saturación predecirá correctamente la rama, excepto en las pocas iteraciones después de que cambie de dirección.
Visualización rápida:
T = rama tomada
N = rama no tomada
datos [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
rama = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (fácil de predecir)
Sin embargo, cuando los datos son completamente aleatorios, el predictor de rama se vuelve inútil porque no puede predecir datos aleatorios. Por lo tanto, probablemente habrá alrededor del 50% de predicciones erróneas (no mejor que una suposición aleatoria).
datos [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
rama = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completamente aleatorio, difícil de predecir)
Entonces, ¿qué puede hacerse?
Si el compilador no puede optimizar la rama en un movimiento condicional, puede probar algunos trucos si está dispuesto a sacrificar la legibilidad por el rendimiento.
Reemplazar:
si (dato [c]> = 128)
suma + = datos [c];
con:
int t = (datos [c] - 128) >> 31;
suma + = ~ t & datos [c];
Esto elimina la rama y la reemplaza con algunas operaciones bit a bit.
(Tenga en cuenta que este truco no es estrictamente equivalente a la sentencia if original. Pero en este caso, es válido para todos los valores de entrada de datos []).
Puntos de referencia: Core i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - Versión x64
// Rama - Aleatorio
segundos = 11,777
// Rama - Ordenado
segundos = 2,352
// Sin ramas - Aleatorio
segundos = 2.564
// Sin ramas - Ordenado
segundos = 2.587
Java - NetBeans 7.1.1 JDK 7 - x64
// Rama - Aleatorio
segundos = 10,93293813
// Rama - Ordenado
segundos = 5.643797077
// Sin ramas -Aleatorio
segundos = 3.113581453
// Sin ramas - Ordenado
segundos = 3,186068823
Observaciones:
Con la rama: Existe una gran diferencia entre los datos ordenados y no ordenados.
Con el truco: no hay diferencia entre datos ordenados y no ordenados.
En el caso de C ++, el truco es en realidad un poco más lento que con la rama cuando se ordenan los datos.
Una regla general es evitar las bifurcaciones dependientes de datos en bucles críticos (como en este ejemplo).
Actualizar:
GCC 4.6.1 con -O3 o -ftree-vectorize en x64 puede generar un movimiento condicional. Por tanto, no hay diferencia entre los datos ordenados y no ordenados; ambos son rápidos.
(O algo rápido: para el caso ya ordenado, cmov puede ser más lento, especialmente si GCC lo coloca en la ruta crítica en lugar de simplemente agregar, especialmente en Intel antes de Broadwell, donde cmov tiene latencia de 2 ciclos: gcc optimization flag -O3 hace que el código sea más lento que -O2)
VC ++ 2010 no puede generar movimientos condicionales para esta rama incluso bajo / Ox.
El compilador Intel C ++ (ICC) 11 hace algo milagroso. Intercambia los dos bucles, elevando así la rama impredecible al bucle exterior. Por lo tanto, no solo es inmune a las predicciones erróneas, sino que también es dos veces más rápido que lo que VC ++ y GCC puedan generar. En otras palabras, ICC aprovechó el ciclo de prueba para derrotar el punto de referencia ...
Si le da al compilador de Intel el código sin ramificaciones, simplemente lo vectoriza ... y es tan rápido como con la ramificación (con el intercambio de bucle).
Esto demuestra que incluso los compiladores modernos maduros pueden variar enormemente en su capacidad para optimizar el código ...
|
Predicción de ramas.
Con una matriz ordenada, los datos de condición [c]> = 128 primero son falsos para una serie de valores, luego se vuelven verdaderos para todos los valores posteriores. Eso es fácil de predecir. Con una matriz sin clasificar, usted paga el costo de ramificación.
|
La razón por la que el rendimiento mejora drásticamente cuando se ordenan los datos es que se elimina la penalización de predicción de rama, como se explica maravillosamente en la respuesta de Mysticial.
Ahora, si miramos el código
si (dato [c]> = 128)
suma + = datos [c];
podemos encontrar que el significado de esta rama particular if ... else ... es agregar algo cuando se cumple una condición. Este tipo de rama se puede transformar fácilmente en una instrucción de movimiento condicional, que se compilaría en una instrucción de movimiento condicional: cmovl, en un sistema x86. Se elimina la ramificación y, por tanto, la penalización de predicción de ramificación potencial.
En C, por lo tanto C ++, la declaración, que se compilaría directamente (sin ninguna optimización) en la instrucción de movimiento condicional en x86, ¿es el operador ternario ...? ...: .... Entonces reescribimos la declaración anterior en una equivalente:
suma + = datos [c]> = 128? dato [c]: 0;
Mientras mantenemos la legibilidad, podemos verificar el factor de aceleración.
En un Intel Core i7-2600K @ 3.4 GHz y Visual Studio 2010 Release Mode, el punto de referencia es (formato copiado de Mysticial):
x86
// Rama - Aleatorio
segundos = 8.885
// Rama - Ordenado
segundos = 1.528
// Sin ramas - Aleatorio
segundos = 3.716
// Sin ramas - Ordenado
segundos = 3,71
x64
// Rama - Aleatorio
segundos = 11,302
// Rama - Ordenado
segundos = 1.830
// Sin ramas - Aleatorio
segundos = 2.736
// Sin ramas - Ordenado
segundos = 2.737
El resultado es robusto en múltiples pruebas. Obtenemos una gran aceleración cuando el resultado de la rama es impredecible, pero sufrimos un poco cuando es predecible. De hecho, cuando se usa un movimiento condicional, el rendimiento es el mismo independientemente del patrón de datos.
Ahora miremos más de cerca investigando el ensamblado x86 que generan. Para simplificar, usamos dos funciones max1 y max2.
max1 usa la rama condicional if ... else ...:
int max1 (int a, int b) {
si (a> b)
return a;
más
volver b;
}
max2 usa el operador ternario ...? ...: ...:
int max2 (int a, int b) {
volver a> b? a: b;
}
En una máquina x86-64, GCC -S genera el siguiente ensamblado.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
salir
retirado
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
salir
retirado
max2 usa mucho menos código debido al uso de la instrucción cmovge. Pero la ganancia real es que max2 no implica saltos de rama, jmp, lo que tendría una penalización de rendimiento significativa si el resultado predicho no es correcto.
Entonces, ¿por qué un movimiento condicional funciona mejor?
En un procesador x86 típico, la ejecución de una instrucción se divide en varias etapas. Aproximadamente, tenemos hardware diferente para lidiar con diferentes etapas. Por tanto, no tenemos que esperar a que termine una instrucción para empezar una nueva. Esto se llama canalización.
En un caso de bifurcación, la siguiente instrucción está determinada por la anterior, por lo que no podemos realizar la canalización. Tenemos que esperar o predecir.
En un caso de movimiento condicional,la instrucción de movimiento condicional de ejecución se divide en varias etapas, pero las etapas anteriores como Fetch y Decode no dependen del resultado de la instrucción anterior; sólo las últimas etapas necesitan el resultado. Por lo tanto, esperamos una fracción del tiempo de ejecución de una instrucción. Es por eso que la versión de movimiento condicional es más lenta que la rama cuando la predicción es fácil.
El libro Computer Systems: A Programmer's Perspective, segunda edición, explica esto en detalle. Puede consultar la Sección 3.6.6 para las Instrucciones de movimiento condicional, el Capítulo 4 completo para la Arquitectura del procesador y la Sección 5.11.2 para obtener un tratamiento especial para las sanciones por predicción de rama y predicción errónea.
A veces, algunos compiladores modernos pueden optimizar nuestro código para ensamblar con un mejor rendimiento, a veces algunos compiladores no pueden (el código en cuestión usa el compilador nativo de Visual Studio). Conocer la diferencia de rendimiento entre una rama y un movimiento condicional cuando es impredecible puede ayudarnos a escribir código con mejor rendimiento cuando el escenario se vuelve tan complejo que el compilador no puede optimizarlos automáticamente.
|
Si tiene curiosidad acerca de más optimizaciones que se pueden hacer en este código, considere esto:
Comenzando con el bucle original:
para (sin signo i = 0; i <100000; ++ i)
{
para (sin signo j = 0; j  = 128)
suma + = datos [j];
}
}
Con el intercambio de bucles, podemos cambiar este bucle con seguridad a:
para (sin signo j = 0; j  = 128)
suma + = datos [j];
}
}
Luego, puede ver que el condicional if es constante durante la ejecución del ciclo i, por lo que puede sacar el if:
para (sin signo j = 0; j  = 128)
{
para (sin signo i = 0; i <100000; ++ i)
{
suma + = datos [j];
}
}
}
Luego, verá que el bucle interno se puede contraer en una sola expresión, suponiendo que el modelo de punto flotante lo permita (/ fp: fast se lanza, por ejemplo)
para (sin signo j = 0; j  = 128)
{
suma + = datos [j] * 100000;
}
}
Ese es 100.000 veces más rápido que antes.
|
Sin duda, algunos de nosotros estaríamos interesados ​​en formas de identificar el código que es problemático para el predictor de rama de la CPU. La herramienta Valgrind cachegrind tiene un simulador de predicción de rama, habilitado mediante el uso de la marca --branch-sim = yes. Al ejecutarlo sobre los ejemplos de esta pregunta, con el número de bucles externos reducido a 10000 y compilado con g ++, se obtienen estos resultados:
Ordenado:
== 32551 == Sucursales: 656,645,130 (656,609,208 cond + 35,922 ind)
== 32551 == Predicciones erróneas: 169,556 (169,095 cond + 461 ind)
== 32551 == Tasa de errores de interpretación: 0,0% (0,0% + 1,2%)
Sin clasificar:
== 32555 == Sucursales: 655,996,082 (655,960,160 cond + 35,922 ind)
== 32555 == Predicciones erróneas: 164,073,152 (164,072,692 cond + 460 ind)
== 32555 == Tasa de errores de interpretación: 25,0% (25,0% + 1,2%)
Profundizando en la salida línea por línea producida por cg_annotate, vemos para el ciclo en cuestión:
Ordenado:
Bc Bcm Bi Bim
10,001 4 0 0 para (sin signo i = 0; i <10000; ++ i)
. . . . {
. . . . // bucle primario
327,690,000 10,016 0 0 para (sin signo c = 0; c  = 128)
0 0 0 0 suma + = datos [c];
. . . . }
. . . . }
Sin clasificar:
Bc Bcm Bi Bim
10,001 4 0 0 para (sin signo i = 0; i <10000; ++ i)
. . . . {
. . . . // bucle primario
327,690,000 10,038 0 0 para (sin signo c = 0; c  = 128)
0 0 0 0 suma + = datos [c];
. . . . }
. . . . }
Esto le permite identificar fácilmente la línea problemática: en la versión sin clasificar, la línea if (data [c]> = 128) está causando 164,050,007 ramas condicionales mal pronosticadas (Bcm) bajo el modelo de predicción de ramas de cachegrind, mientras que solo está causando 10,006 en la versión ordenada .
Como alternativa, en Linux puede utilizar el subsistema de contadores de rendimiento para realizar la misma tarea, pero con rendimiento nativo utilizando contadores de CPU.
perf stat ./sumtest_sorted
Ordenado:
Estadísticas del contador de rendimiento para './sumtest_sorted':
11808.095776 reloj de tareas # 0.998 CPU utilizadas
1.062 cambios de contexto # 0.090 K / seg
14 CPU-migraciones # 0.001 K / seg
337 fallas de página # 0.029 K / seg
26,487,882,764 ciclos # 2.243 GHz
41,025,654,322 instrucciones # 1.55 insns por ciclo
6.558.871.379 sucursales # 555.455 M / seg
567,204 sucursales perdidas # 0.01% de todas las sucursales
11.827228330 segundos de tiempo transcurrido
Sin clasificar:
Actuaciónestadísticas de contador para './sumtest_unsorted':
28877.954344 reloj de tareas # 0.998 CPU utilizadas
2.584 conmutadores de contexto # 0.089 K / seg
18 CPU-migraciones # 0.001 K / seg
335 fallas de página # 0.012 K / seg
65,076,127,595 ciclos # 2.253 GHz
41,032,528,741 instrucciones # 0.63 insns por ciclo
6.560.579.013 sucursales # 227.183 M / seg
1,646,394,749 sucursales # 25.10% de todas las sucursales
28.935500947 segundos de tiempo transcurrido
También puede hacer anotaciones de código fuente con desmontaje.
perf record -e branch-miss ./sumtest_unsorted
perf anotar -d sumtest_unsorted
Por ciento | Código fuente y desmontaje de sumtest_unsorted
------------------------------------------------
...
: suma + = datos [c];
0.00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0.00: 400a28: agregar% rax, -0x30 (% rbp)
...
Consulte el tutorial de rendimiento para obtener más detalles.
|
Acabo de leer esta pregunta y sus respuestas, y siento que falta una respuesta.
Una forma común de eliminar la predicción de rama que encontré que funciona particularmente bien en lenguajes administrados es una búsqueda de tabla en lugar de usar una rama (aunque no la he probado en este caso).
Este enfoque funciona en general si:
es una tabla pequeña y es probable que se almacene en caché en el procesador, y
está ejecutando las cosas en un bucle bastante estrecho y / o el procesador puede precargar los datos.
Antecedentes y por que
Desde la perspectiva del procesador, su memoria es lenta. Para compensar la diferencia de velocidad, su procesador incorpora un par de cachés (caché L1 / L2). Así que imagina que estás haciendo tus buenos cálculos y descubre que necesitas un poco de memoria. El procesador obtendrá su operación de "carga" y cargará la parte de la memoria en la caché, y luego usará la caché para hacer el resto de los cálculos. Debido a que la memoria es relativamente lenta, esta "carga" ralentizará su programa.
Al igual que la predicción de rama, esto se optimizó en los procesadores Pentium: el procesador predice que necesita cargar un dato e intenta cargarlo en la caché antes de que la operación llegue realmente a la caché. Como ya hemos visto, la predicción de rama a veces sale terriblemente mal; en el peor de los casos, debe volver atrás y esperar una carga de memoria, lo que llevará una eternidad (en otras palabras: la predicción de rama fallida es mala, una memoria cargar después de un error de predicción de rama es simplemente horrible!).
Afortunadamente para nosotros, si el patrón de acceso a la memoria es predecible, el procesador lo cargará en su caché rápido y todo estará bien.
Lo primero que debemos saber es qué es pequeño. Si bien lo más pequeño es generalmente mejor, una regla general es ceñirse a las tablas de búsqueda que tienen un tamaño <= 4096 bytes. Como límite superior: si su tabla de búsqueda es mayor que 64K, probablemente valga la pena reconsiderarlo.
Construyendo una mesa
Entonces hemos descubierto que podemos crear una mesa pequeña. Lo siguiente que debe hacer es instalar una función de búsqueda. Las funciones de búsqueda suelen ser funciones pequeñas que utilizan un par de operaciones básicas con números enteros (y, o, xor, desplazar, sumar, eliminar y quizás multiplicar). Desea que la función de búsqueda traduzca su entrada a algún tipo de 'clave única' en su tabla, que luego simplemente le da la respuesta de todo el trabajo que deseaba que hiciera.
En este caso:> = 128 significa que podemos mantener el valor, <128 significa que nos deshacemos de él. La forma más sencilla de hacerlo es usando un 'Y': si lo mantenemos, lo hacemos Y con 7FFFFFFF; si queremos deshacernos de él, lo hacemos Y con 0. Note también que 128 es una potencia de 2, por lo que podemos seguir adelante y hacer una tabla de 32768/128 enteros y llenarla con un cero y muchos 7FFFFFFFF's.
Idiomas gestionados
Quizás se pregunte por qué esto funciona bien en lenguajes administrados. Después de todo, los lenguajes administrados verifican los límites de las matrices con una rama para asegurarse de que no se equivoque ...
Bueno no exactamente... :-)
Ha habido bastante trabajo para eliminar esta rama para lenguajes administrados. Por ejemplo:
para (int i = 0; i  = 128)? c: 0;
}
// Prueba
DateTime startTime = System.DateTime.Now;
suma larga = 0;
para (int i = 0; i <100000; ++ i)
{
// Bucle primario
para (int j = 0; j  = 128. Eso significa que podemos extraer fácilmente un solo bit que nos dirá si queremos un valor o no: cambiando los datos a la derecha de 7 bits, nos queda un 0 bit o un 1 bit, y solo queremos sumar el valor cuando tenemos un 1 bit. Llamemos a este bit el "bit de decisión".
Al usar el valor 0/1 del bit de decisión como índice en una matriz, podemos crear un código que será igualmente rápido, ya sea que los datos estén ordenados o no. Nuestro código siempre agregará un valor, pero cuando el bit de decisión sea 0, agregaremos el valor en algún lugar que no nos importe. Aquí está el código:
// Prueba
clock_t start = clock ();
long long a [] = {0, 0};
suma larga larga;
para (sin signo i = 0; i <100000; ++ i)
{
// Bucle primario
para (sin signo c = 0; c > 7);
a [j] + = datos [c];
}
}
double elapsedTime = static_cast  (reloj () - inicio) / CLOCKS_PER_SEC;
suma = a [1];
Este código desperdicia la mitad de las adiciones pero nunca tiene un error de predicción de rama. Es tremendamente más rápido en datos aleatorios que la versión con una declaración if real.
Pero en mis pruebas, una tabla de búsqueda explícita fue un poco más rápida que esta, probablemente porque la indexación en una tabla de búsqueda fue un poco más rápida que el cambio de bits. Esto muestra cómo mi código configura y usa la tabla de búsqueda (llamada sin imaginación lut para "Tabla de búsqueda" en el código). Aquí está el código C ++:
// Declare y luego complete la tabla de búsqueda
int lut [256];
para (sin signo c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Usa la tabla de búsqueda después de que esté construida
para (sin signo i = 0; i <100000; ++ i)
{
// Bucle primario
para (sin firmar c = 0; c  valor)
nodo = nodo-> pLeft;
más
nodo = nodo-> pRight;
esta biblioteca haría algo como:
i = (x  valor);
nodo = nodo-> enlace [i];
Aquí hay un enlace a este código: Red Black Trees, Eternally Confuzzled
|
En el caso ordenado, puede hacerlo mejor que confiar en una predicción de rama exitosa o cualquier truco de comparación sin ramas: elimine completamente la rama.
De hecho, la matriz está particionada en una zona contigua con datos <128 y otra con datos> = 128. Por lo tanto, debe encontrar el punto de partición con una búsqueda dicotómica (usando Lg (arraySize) = 15 comparaciones), luego haga una acumulación directa desde ese punto.
Algo como (sin marcar)
int i = 0, j, k = arraySize;
mientras (i > 1;
si (dato [j]> = 128)
k = j;
más
i = j;
}
suma = 0;
para (; i > 1;
para (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
para (suma = 0; i  = 128)
/ \
/ \
/ \
verdadero Falso
/ \
/ \
/ \
/ \
B) suma + = datos [c]; C) para bucle o impresión ().
Sin la predicción de rama, ocurriría lo siguiente:
Para ejecutar la instrucción B o la instrucción C, el procesador tendrá que esperar hasta que la instrucción A no llegue hasta la etapa EX en la tubería, ya que la decisión de ir a la instrucción B o la instrucción C depende del resultado de la instrucción A. Entonces la tubería se verá así.
cuando si la condición devuelve verdadero:
Cuando la condición if devuelve falso:
Como resultado de esperar el resultado de la instrucción A, el total de ciclos de CPU gastados en el caso anterior (sin predicción de bifurcación; tanto para verdadero como para falso) es 7.
Entonces, ¿qué es la predicción de ramas?
El predictor de rama intentará adivinar en qué dirección irá una rama (una estructura if-then-else) antes de que se sepa con certeza. No esperará a que la instrucción A alcance la etapa EX de la tubería, sino que adivinará la decisión e irá a esa instrucción (B o C en el caso de nuestro ejemplo).
En caso de una suposición correcta, la canalización se parece a esto:
Si más tarde se detecta que la suposición fue incorrecta, las instrucciones parcialmente ejecutadas se descartan y la tubería comienza de nuevo con la rama correcta, incurriendo en un retraso.
El tiempo que se pierde en caso de una predicción errónea de la rama es igual al número de etapas en la canalización desde la etapa de recuperación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener tuberías bastante largas, por lo que el retraso de predicción errónea está entre 10 y 20 ciclos de reloj. Cuanto más larga sea la canalización, mayor será la necesidad de un buen predictor de rama.
En el código del OP, la primera vez que el condicional, el predictor de rama no tiene ninguna información para basar la predicción, la primera vez elegirá al azar la siguiente instrucción. Más adelante en el ciclo for, puede basar la predicción en el historial.
Para una matriz ordenada en orden ascendente, hay tres posibilidades:
Todos los elementos son menos de 128
Todos los elementos son mayores que 128
Algunos elementos nuevos iniciales son menos de 128 y luego se vuelven mayores de 128
Supongamos que el predictor siempre asumirá la rama verdadera en la primera ejecución.
Entonces, en el primer caso, siempre se tomará el verdaderorama ya que históricamente todas sus predicciones son correctas.
En el segundo caso, inicialmente predecirá incorrectamente, pero después de algunas iteraciones, predecirá correctamente.
En el tercer caso, inicialmente predecirá correctamente hasta que los elementos sean inferiores a 128. Después de lo cual fallará durante algún tiempo y se corregirá cuando vea una falla en la predicción de rama en el historial.
En todos estos casos, la falla será demasiado menor y, como resultado, solo unas pocas veces será necesario descartar las instrucciones parcialmente ejecutadas y comenzar de nuevo con la rama correcta, lo que resultará en menos ciclos de CPU.
Pero en el caso de una matriz aleatoria no ordenada, la predicción deberá descartar las instrucciones parcialmente ejecutadas y comenzar de nuevo con la rama correcta la mayor parte del tiempo y generar más ciclos de CPU en comparación con la matriz ordenada.
|
Una respuesta oficial sería de
Intel: evitar el costo de predicciones erróneas de sucursales
Intel - Reorganización de sucursales y bucles para evitar predicciones erróneas
Artículos científicos - arquitectura informática de predicción de ramas
Libros: J.L. Hennessy, D.A. Patterson: Arquitectura informática: un enfoque cuantitativo
Artículos en publicaciones científicas: T.Y. Sí, Y.N. Patt hizo muchos de estos en predicciones de rama.
También puede ver en este hermoso diagrama por qué se confunde el predictor de rama.
Cada elemento del código original es un valor aleatorio
datos [c] = std :: rand ()% 256;
por lo que el predictor cambiará de lado cuando el std :: rand () sople.
Por otro lado, una vez ordenado, el predictor se moverá primero a un estado de fuertemente no tomado y cuando los valores cambien al valor alto, el predictor cambiará en tres ciclos desde fuertemente no tomado a fuertemente tomado.
|
En la misma línea (creo que esto no fue resaltado por ninguna respuesta) es bueno mencionar que a veces (especialmente en el software donde el rendimiento es importante, como en el kernel de Linux) puede encontrar algunas declaraciones if como las siguientes:
si (probablemente (todo_es_o))
{
/* Hacer algo */
}
o similar:
if (poco probable (muy_improbable_condición))
{
/* Hacer algo */
}
Tanto probable () como improbable () son de hecho macros que se definen usando algo como __builtin_expect de GCC para ayudar al compilador a insertar código de predicción para favorecer la condición teniendo en cuenta la información proporcionada por el usuario. GCC soporta otras incorporaciones que podrían cambiar el comportamiento del programa en ejecución o emitir instrucciones de bajo nivel como borrar la caché, etc. Consulte esta documentación que analiza las incorporaciones de GCC disponibles.
Normalmente, este tipo de optimizaciones se encuentran principalmente en aplicaciones de tiempo real duro o sistemas integrados donde el tiempo de ejecución importa y es crítico. Por ejemplo, si está verificando alguna condición de error que solo ocurre 1/10000000 veces, ¿por qué no informar al compilador sobre esto? De esta forma, de forma predeterminada, la predicción de la rama supondría que la condición es falsa.
|
Las operaciones booleanas de uso frecuente en C ++ producen muchas ramas en el programa compilado. Si estas ramas están dentro de bucles y son difíciles de predecir, pueden ralentizar la ejecución de manera significativa. Las variables booleanas se almacenan como enteros de 8 bits con el valor 0 para falso y 1 para verdadero.
Las variables booleanas están sobredeterminadas en el sentido de que todos los operadores que tienen variables booleanas como entrada verifican si las entradas tienen algún otro valor que 0 o 1, pero los operadores que tienen booleanos como salida no pueden producir otro valor que 0 o 1. Esto hace operaciones con Las variables booleanas como entrada son menos eficientes de lo necesario.
Considere el ejemplo:
bool a, b, c, d;
c = a && b;
d = a || segundo;
Normalmente, el compilador lo implementa de la siguiente manera:
bool a, b, c, d;
si (a! = 0) {
si (b! = 0) {
c = 1;
}
else {
goto CFALSE;
}
}
else {
CFALSE:
c = 0;
}
si (a == 0) {
si (b == 0) {
d = 0;
}
else {
goto DTRUE;
}
}
else {
VERDADERO:
d = 1;
}
Este código está lejos de ser óptimo. Las ramas pueden tardar bastante en caso de errores de predicción. Las operaciones booleanas pueden hacerse mucho más eficientes si se sabe con certeza que los operandos no tienen otros valores que 0 y 1. La razón por la que el compilador no hace tal suposición es que las variables podrían tener otros valores si no están inicializadas o provienen de fuentes desconocidas. El código anterior se puede optimizar si a y b se han inicializado a valores válidos o si provienen de operadores que producen una salida booleana. El código optimizado se ve así:
char a = 0, b = 1, c, d;
c = a & b;
d = a | segundo;
char se usa en lugar de bool para que sea posible usar los operadores bit a bit (& y |) en lugar de los operadores booleanos (&& y ||). Los operadores bit a bit son instrucciones únicas que toman solo un ciclo de reloj. El operador OR (|) funciona incluso si ayb tienen valores distintos de 0 o 1. El operador AND (&) y el operador OR EXCLUSIVO (^) pueden dar resultados inconsistentes si los operandos tienen valores distintos de 0 y 1.
~ no se puede utilizar para NOT. En lugar,puede hacer un NO booleano en una variable que se sabe que es 0 o 1 haciendo XOR con 1:
bool a, b;
b =! a;
se puede optimizar para:
char a = 0, b;
b = a ^ 1;
a && b no se puede reemplazar con a & b si b es una expresión que no debe evaluarse si a es falsa (&& no evaluará by & will). Asimismo, un || b no se puede reemplazar por a | b si b es una expresión que no debe evaluarse si a es verdadera.
El uso de operadores bit a bit es más ventajoso si los operandos son variables que si los operandos son comparaciones:
bool a; doble x, y, z;
a = x> y && z <5,0;
es óptimo en la mayoría de los casos (a menos que espere que la expresión && genere muchas predicciones erróneas de rama).
|
¡Eso es seguro!...
¡La predicción de rama hace que la lógica se ejecute más lentamente, debido al cambio que ocurre en su código! Es como si estuvieras yendo por una calle recta o una calle con muchos giros, ¡seguro que la recta se va a hacer más rápido! ...
Si la matriz está ordenada, su condición es falsa en el primer paso: datos [c]> = 128, luego se convierte en un valor verdadero para todo el camino hasta el final de la calle. Así es como llegas más rápido al final de la lógica. Por otro lado, al usar una matriz sin clasificar, necesita mucho giro y procesamiento, lo que hace que su código se ejecute más lento con seguridad ...
Mira la imagen que creé para ti a continuación. ¿Qué calle se terminará más rápido?
Entonces, programáticamente, la predicción de ramas hace que el proceso sea más lento ...
Además, al final, es bueno saber que tenemos dos tipos de predicciones de rama de que cada una afectará tu código de manera diferente:
1. Estático
2. Dinámico
El microprocesador utiliza la predicción de rama estática la primera vez
se encuentra una rama condicional, y la predicción de rama dinámica es
utilizado para ejecuciones sucesivas del código de rama condicional.
Para escribir su código de manera efectiva y aprovechar estos
reglas, al escribir declaraciones if-else o switch, marque la mayoría
los casos comunes primero y trabajar progresivamente hasta el menos común.
Los bucles no requieren necesariamente un orden especial de código para
predicción de rama estática, como solo la condición del iterador de bucle
se utiliza normalmente.
|
Esta pregunta ya ha sido respondida excelentemente muchas veces. Aún así, me gustaría llamar la atención del grupo sobre otro análisis interesante.
Recientemente, este ejemplo (modificado muy levemente) también se utilizó como una forma de demostrar cómo se puede perfilar un fragmento de código dentro del programa mismo en Windows. En el camino, el autor también muestra cómo usar los resultados para determinar dónde pasa el código la mayor parte del tiempo, tanto en el caso ordenado como sin clasificar. Finalmente, la pieza también muestra cómo usar una característica poco conocida de HAL (Capa de abstracción de hardware) para determinar cuánta predicción errónea de rama está sucediendo en el caso sin clasificar.
El enlace está aquí:
Una demostración de autoperfilado
|
Como ya ha sido mencionado por otros, lo que se esconde detrás del misterio es Branch Predictor.
No estoy tratando de agregar algo, sino de explicar el concepto de otra manera.
Hay una introducción concisa en la wiki que contiene texto y diagrama.
Me gusta la explicación a continuación, que usa un diagrama para elaborar el Predictor de ramas de manera intuitiva.
En arquitectura de computadora, un predictor de rama es un
circuito digital que intenta adivinar de qué manera una rama (por ejemplo, un
estructura if-then-else) irá antes de que esto se sepa con seguridad. los
El propósito del predictor de rama es mejorar el flujo en el
canalización de instrucciones. Los predictores de rama juegan un papel fundamental en
logrando un alto rendimiento efectivo en muchas tuberías modernas
arquitecturas de microprocesador como x86.
La ramificación bidireccional generalmente se implementa con un salto condicional
instrucción. Un salto condicional puede "no tomarse" y continuar
ejecución con la primera rama de código que sigue inmediatamente
después del salto condicional, o se puede "tomar" y saltar a un
lugar diferente en la memoria del programa donde se encuentra la segunda rama del código
almacenado. No se sabe con certeza si un salto condicional será
tomado o no tomado hasta que se haya calculado la condición y el
el salto condicional ha pasado la etapa de ejecución en la instrucción
tubería (ver fig. 1).
Basado en el escenario descrito, he escrito una demostración de animación para mostrar cómo se ejecutan las instrucciones en una tubería en diferentes situaciones.
Sin el predictor de ramas.
Sin la predicción de rama, el procesador tendría que esperar hasta que
La instrucción de salto condicional ha pasado la etapa de ejecución antes de que
la siguiente instrucción puede entrar en la etapa de recuperación en la canalización.
El ejemplo contiene tres instrucciones y la primera es una instrucción de salto condicional. Las dos últimas instrucciones pueden entrar en la canalización hasta que se ejecute la instrucción de salto condicional.
Se necesitarán 9 ciclos de reloj para completar 3 instrucciones.
Utilice el Predictor de ramas y no realice un salto condicional. Supongamos que la predicción no está tomando elsalto condicional.
Se necesitarán 7 ciclos de reloj para completar 3 instrucciones.
Utilice el Predictor de ramas y realice un salto condicional. Supongamos que la predicción no está dando el salto condicional.
Se necesitarán 9 ciclos de reloj para completar 3 instrucciones.
El tiempo que se pierde en caso de una predicción errónea de rama es igual a
el número de etapas en la tubería desde la etapa de recuperación hasta la
ejecutar etapa. Los microprocesadores modernos tienden a tener bastante
tuberías de modo que el retardo de predicción errónea esté entre 10 y 20 horas
ciclos. Como resultado, alargar una tubería aumenta la necesidad de
predictor de rama más avanzado.
Como puede ver, parece que no tenemos una razón para no usar el Predictor de ramas.
Es una demostración bastante simple que aclara la parte muy básica de Branch Predictor. Si esos gifs son molestos, no dude en eliminarlos de la respuesta y los visitantes también pueden obtener el código fuente de demostración en vivo de BranchPredictorDemo
|
¡Ganancia de predicción de ramas!
Es importante comprender que la predicción errónea de las ramas no ralentiza los programas. El costo de una predicción perdida es como si la predicción de rama no existiera y esperaras la evaluación de la expresión para decidir qué código ejecutar (más explicación en el siguiente párrafo).
if (expresión)
{
// Ejecutar 1
} más {
// Ejecutar 2
}
Siempre que haya una instrucción if-else \ switch, la expresión debe evaluarse para determinar qué bloque debe ejecutarse. En el código ensamblador generado por el compilador, se insertan instrucciones de bifurcación condicionales.
Una instrucción de bifurcación puede hacer que una computadora comience a ejecutar una secuencia de instrucción diferente y, por lo tanto, se desvíe de su comportamiento predeterminado de ejecutar instrucciones en orden (es decir, si la expresión es falsa, el programa omite el código del bloque if) dependiendo de alguna condición, que es la evaluación de la expresión en nuestro caso.
Dicho esto, el compilador intenta predecir el resultado antes de que se evalúe realmente. Obtendrá instrucciones del bloque if, y si la expresión resulta ser verdadera, ¡maravilloso! Ganamos el tiempo necesario para evaluarlo y progresamos en el código; de lo contrario, estamos ejecutando el código incorrecto, la canalización se vacía y se ejecuta el bloque correcto.
Visualización:
Digamos que necesita elegir la ruta 1 o la ruta 2. Esperando a que su compañero revise el mapa, se detuvo en ## y esperó, o simplemente podría elegir la ruta 1 y, si tiene suerte (la ruta 1 es la ruta correcta), Entonces, genial, no tuvo que esperar a que su compañero revisara el mapa (usted ahorró el tiempo que le habría tomado revisar el mapa), de lo contrario, simplemente regresará.
Si bien la limpieza de tuberías es súper rápida, hoy en día vale la pena arriesgarse. Predecir datos ordenados o datos que cambian lentamente siempre es más fácil y mejor que predecir cambios rápidos.
O Ruta 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Ruta 2 \ --------------------------------
|
En ARM, no se necesita una bifurcación, porque cada instrucción tiene un campo de condición de 4 bits, que prueba (a costo cero) cualquiera de las 16 condiciones diferentes que pueden surgir en el Registro de estado del procesador, y si la condición en una instrucción es falso, se omite la instrucción. Esto elimina la necesidad de bifurcaciones cortas y no habría ningún resultado de predicción de bifurcaciones para este algoritmo. Por lo tanto, la versión ordenada de este algoritmo funcionaría más lentamente que la versión sin clasificar en ARM, debido a la sobrecarga adicional de clasificación.
El bucle interno de este algoritmo se parecería al siguiente en lenguaje ensamblador ARM:
MOV R0, # 0 // R0 = suma = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = dirección de la matriz de datos (coloque esta instrucción fuera del bucle externo)
.inner_loop // Etiqueta de rama de bucle interno
LDRB R3, [R2, R1] // R3 = datos [c]
CMP R3, # 128 // compare R3 con 128
ADDGE R0, R0, R3 // si R3> = 128, entonces suma + = datos [c] - ¡no se necesita rama!
AÑADIR R1, R1, # 1 // c ++
CMP R1, #arraySize // comparar c con arraySize
BLT inner_loop // Se ramifica a inner_loop si c  ());
para (sin signo c = 0; c  = 128
suma = suma + datos1 (j);
fin
fin
fin
toc;
ExeTimeWithSorting = toc - tic;
Los resultados para el código MATLAB anterior son los siguientes:
a: Tiempo transcurrido (sin clasificación) = 3479,880861 segundos.
b: Tiempo transcurrido (con clasificación) = 2377,873098 segundos.
Los resultados del código C como en @GManNickG obtengo:
a: Tiempo transcurrido (sin clasificación) = 19,8761 seg.
b: Tiempo transcurrido (con clasificación) = 7.37778 seg.
En base a esto, parece que MATLAB es casi 175 veces más lento que la implementación de C sin clasificación y 350 veces más lento con clasificación. En otras palabras, el efecto (de la predicción de rama) es 1,46x para la implementación de MATLAB y 2,7x para la implementación de C.
|
La suposición de otras respuestas de que es necesario ordenar los datos no es correcta.
El siguiente código no ordena toda la matriz, sino solo segmentos de 200 elementos y, por lo tanto, se ejecuta más rápido.
Ordenar solo las secciones de k elementos completa el preprocesamiento en tiempo lineal, O (n), en lugar del tiempo O (n.log (n)) necesario para ordenar toda la matriz.
#include 
#include 
#include 
int main () {
int data [32768]; const int l = tamaño de los datos / tamaño de los datos [0];
para (sin signo c = 0; c  = 128)
suma + = datos [c];
}
}
std :: cout << static_cast  (reloj () - inicio) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "suma =" << suma << std :: endl;
}
Esto también "prueba" que no tiene nada que ver con ningún problema algorítmico, como el orden de clasificación, y de hecho es una predicción de rama.
|
Respuesta de Bjarne Stroustrup a esta pregunta:
Suena como una pregunta de entrevista. ¿Es verdad? ¿Cómo sabrías? Es una mala idea responder preguntas sobre eficiencia sin antes hacer algunas mediciones, por lo que es importante saber cómo medir.
Entonces, probé con un vector de un millón de enteros y obtuve:
Ya ordenados 32995 milisegundos
Mezclado 125944 milisegundos
Ya ordenados 18610 milisegundos
Barajado 133304 milisegundos
Ya ordenado 17942 milisegundos
Mezclado 107858 milisegundos
Lo ejecuté varias veces para estar seguro. Sí, el fenómeno es real. Mi código clave era:
ejecución vacía (vector  & v, cadena constante y etiqueta)
{
auto t0 = system_clock :: ahora ();
ordenar (v.begin (), v.end ());
auto t1 = system_clock :: ahora ();
cout << etiqueta
<< duration_cast  (t1 - t0) .count ()
<< "milisegundos \ n";
}
tst vacío ()
{
vector  v (1'000'000);
iota (v.begin (), v.end (), 0);
ejecutar (v, "ya ordenado");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: dispositivo_aleatorio {} ()});
ejecutar (v, "barajado");
}
Al menos el fenómeno es real con este compilador, biblioteca estándar y configuraciones de optimizador. Diferentes implementaciones pueden dar y dan respuestas diferentes. De hecho, alguien hizo un estudio más sistemático (una búsqueda rápida en la web lo encontrará) y la mayoría de las implementaciones muestran ese efecto.
Una razón es la predicción de ramas: la operación clave en el algoritmo de ordenación es “si (v [i]  = 128. Eso significa que podemos extraer fácilmente un solo bit que nos dirá si queremos un valor o no: cambiando los datos a la derecha de 7 bits, nos queda un 0 bit o un 1 bit, y solo queremos sumar el valor cuando tenemos un 1 bit. Llamemos a este bit el "bit de decisión".
Al usar el valor 0/1 del bit de decisión como índice en una matriz, podemos crear un código que será igualmente rápido, ya sea que los datos estén ordenados o no. Nuestro código siempre agregará un valor, pero cuando el bit de decisión sea 0, agregaremos el valor en algún lugar que no nos importe. Aquí está el código:
// Prueba
clock_t start = clock ();
long long a [] = {0, 0};
suma larga larga;
para (sin signo i = 0; i <100000; ++ i)
{
// Bucle primario
para (sin firmar c = 0; c > 7);
a [j] + = datos [c];
}
}
double elapsedTime = static_cast  (reloj () - inicio) / CLOCKS_PER_SEC;
suma = a [1];
Este código desperdicia la mitad de las adiciones pero nunca tiene un error de predicción de rama. Es tremendamente más rápido en datos aleatorios que la versión con una declaración if real.
Pero en mis pruebas, una tabla de búsqueda explícita fue un poco más rápida que esta, probablemente porque la indexación en una tabla de búsqueda fue un poco más rápida que el cambio de bits. Esto muestra cómo mi código configura y usa la tabla de búsqueda (llamada sin imaginación lut para "Tabla de búsqueda" en el código). Aquí está el código C ++:
// Declare y luego complete la tabla de búsqueda
int lut [256];
para (sin signo c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Usa la tabla de búsqueda después de que esté construida
para (sin signo i = 0; i <100000; ++ i)
{
// Bucle primario
para (sin firmar c = 0; c  valor)
nodo = nodo-> pLeft;
más
nodo = nodo-> pRight;
esta biblioteca haría algo como:
i = (x  valor);
nodo = nodo-> enlace [i];
Es una buena solución y tal vez funcione.
|
Pregunta muy activa. Gana 10 de reputación para responder a esta pregunta. El requisito de reputación ayuda a proteger esta pregunta del spam y de la actividad sin respuesta.
No es la respuesta que estás buscando? Lea otras preguntas en las etiquetas java c ++ performance optimization branch-prediction o formule su propia pregunta.